//
// Created by Lantz on 2024/6/7.
//
//#include <iostream>
//#include <vector>
#include <bits/stdc++.h>

using namespace std;
/**
 * 最长公共子序列长度
 * @param m
 * @param n
 * @param x
 * @param y
 * @param c 记录子序列匹配长度  最优值
 * @param b 标记子序列的最优解 1 表示 x[i] == y[j]
 *                         2 表示 c[i-1][j] >= c[i][j-1] 左边大于等于下边的
 *                         3 表示 c[i-1][j] < c[i][j-1]
 *  c[i][j] = c[i-1][j-1] + 1
 *              max(c[i][j-1], c[i-1][j])
 */
void LCSLength(int m, int n, char * x, char * y, vector<vector<int>>& c, vector<vector<int>>& b){
    /**
     * 第 0 行第 0 列都为 0
     */
    for (int i = 0; i <= m; ++i) {
        c[i][0] = 0;
    }
    for (int i = 0; i <= n; ++i) {
        c[0][i] = 0;
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (x[i-1] == y[j-1]){
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;
            } else if (c[i-1][j] >= c[i][j-1]){
                c[i][j] = c[i-1][j];
                b[i][j] = 2;
            } else {
                c[i][j] = c[i][j-1];
                b[i][j] = 3;
            }
        }
    }

    cout<<"最长公共子序列最优值二维数组："<<endl;
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            cout<<c[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"最长公共子序列最优解二维数组："<<endl;
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }

}

void LCS(int i, int j, char * x, vector<vector<int>>& b){
    if(i == 0 || j == 0) return;
    if(b[i][j] == 1){
        LCS(i-1, j-1, x, b);
        cout<<x[i-1];
    }else if(b[i][j] == 2){
        LCS(i-1, j, x, b);
    } else {
        LCS(i, j-1, x, b);
    }
}

int main(void){
    int m = 3, n = 5;
    char x[] = {'a', 'c', 'e'};
    char y[] = {'a', 'b', 'c', 'd', 'e'};
//    int **c = {0};
//    int **b = {0};
    vector<vector<int>> c(m + 1, vector<int>(n+1));
    vector<vector<int>> b(m + 1, vector<int>(n+1));
    LCSLength(m, n, x, y, c, b);
    cout<<"最长公共子序列："<<endl;
    LCS(m, n, x, b);

    return 0;
}